{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Unequal Triplets in Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: unequalTriplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中不等三元组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的正整数数组 <code>nums</code> 。请你找出并统计满足下述条件的三元组 <code>(i, j, k)</code> 的数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt; k &lt; nums.length</code></li>\n",
    "\t<li><code>nums[i]</code>、<code>nums[j]</code> 和 <code>nums[k]</code> <strong>两两不同</strong> 。\n",
    "\t<ul>\n",
    "\t\t<li>换句话说：<code>nums[i] != nums[j]</code>、<code>nums[i] != nums[k]</code> 且 <code>nums[j] != nums[k]</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回满足上述条件三元组的数目<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,4,2,4,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>下面列出的三元组均满足题目条件：\n",
    "- (0, 2, 4) 因为 4 != 2 != 3\n",
    "- (1, 2, 4) 因为 4 != 2 != 3\n",
    "- (2, 3, 4) 因为 2 != 4 != 3\n",
    "共计 3 个三元组，返回 3 。\n",
    "注意 (2, 0, 4) 不是有效的三元组，因为 2 &gt; 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,1,1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在满足条件的三元组，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-unequal-triplets-in-array](https://leetcode.cn/problems/number-of-unequal-triplets-in-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-unequal-triplets-in-array](https://leetcode.cn/problems/number-of-unequal-triplets-in-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,4,2,4,3]', '[1,1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x,y,z in combinations(Counter(nums).values(),3):\n",
    "            ans += x*y*z\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = a = 0\n",
    "        n = len(nums)\n",
    "        for b in cnt.values():\n",
    "            c = n - a - b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                l = i\n",
    "                break\n",
    "        for r in range(l+1, n):\n",
    "            if nums[r] != nums[r-1]:\n",
    "                cnt += (r-l)*l*(n-r)\n",
    "                l = r\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        #用字典来统计每个元素的数量\n",
    "        #Counter函数，键为元素，值为元素个数，从大到小排列\n",
    "        dictnums=Counter(nums)\n",
    "        #记录数组的长度\n",
    "        n=len(nums)\n",
    "        #构建三元数组,假设左边元素个数为a，中间元素个数为b，右边元素个数为c\n",
    "        a=0\n",
    "        #初始个数\n",
    "        ans=0\n",
    "        #b对应的元素在字典里\n",
    "        for b in dictnums.values():\n",
    "            #如果个数和为n\n",
    "            c=n-a-b\n",
    "            #则可以判断\n",
    "            ans+=a*b*c\n",
    "            #更新左边元素\n",
    "            a+=b\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans,a,c=0,0,len(nums)\n",
    "        for b in Counter(nums).values():\n",
    "            c-=b\n",
    "            ans+=a*b*c\n",
    "            a+=b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        size=len(nums)\n",
    "        ans=start=0\n",
    "        for i,(x,y) in enumerate(pairwise(nums)):\n",
    "            if x!=y:\n",
    "                ans+=start*(i-start+1)*(size-i-1)\n",
    "                start=i+1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        i = j = 0\n",
    "        while i < n:\n",
    "            while j < n and nums[j] == nums[i]:\n",
    "                j += 1\n",
    "            res += i * (j - i) * (n - j)\n",
    "            i = j\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        n=0\n",
    "        for i in range(len(nums)-2):\n",
    "            for j in range(i+1,len(nums)-1):\n",
    "                for k in range(j+1,len(nums)):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        n+=1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        n = len(nums)\n",
    "        ans = a = 0\n",
    "        for b in cnt.values():\n",
    "            c = n - a - b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0        \n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                if nums[i] != nums[j]:\n",
    "                    for k in range(j+1, n):\n",
    "                        if nums[k] != nums[i] and nums[k] != nums[j]:\n",
    "                            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        if l < 3:\n",
    "            return 0\n",
    "        i = 0\n",
    "        j = 1\n",
    "        k = 2\n",
    "        cnt = 0\n",
    "        for i in range(0, l):\n",
    "            for j in range(i + 1, l):\n",
    "                if nums[i] == nums[j]:\n",
    "                    continue\n",
    "                else:\n",
    "                    for k in range(j + 1, l):\n",
    "                        if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                            cnt += 1\n",
    "                        else :\n",
    "                            continue\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans = t = 0\n",
    "        n = len(nums)\n",
    "        for v in Counter(nums).values():\n",
    "            ans += t*v*(n - t - v)\n",
    "            t += v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        i = j = 0\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            while j < n and nums[i] == nums[j]:\n",
    "                j += 1\n",
    "            res += i * (j - i) * (n - j)\n",
    "            i = j\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = Counter(nums)\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for _, v in count.items():\n",
    "            res += t * v * (n - t - v)\n",
    "            t += v\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i,len(nums)):\n",
    "                if nums[i] != nums[j]:\n",
    "                    for k in range(j,len(nums)):\n",
    "                        if (nums[i]!=nums[k]) and (nums[j]!=nums[k]):\n",
    "                            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        # 哈希表\n",
    "        # 时间O(n), 空间O(n)\n",
    "\n",
    "        ans, a, c = 0, 0, len(nums)\n",
    "        for b in Counter(nums).values():\n",
    "            c -= b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-unequal-triplets-in-array/solutions/1981413/fei-bao-li-zuo-fa-by-endlesscheng-9ekp/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        d = Counter(nums)\n",
    "        n = len(nums)\n",
    "        x = list(d.values())\n",
    "        # print(d,x)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for mid in range(1,len(x)-1):\n",
    "            tem = x[mid]\n",
    "            left += x[mid-1]\n",
    "            ans += left*tem*(n-left-tem)\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans, start = 0, 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] != nums[i+1]:\n",
    "                ans += start * (i-start+1) * (len(nums)-i-1)\n",
    "                start = i+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        # 暴力\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            d[num] += 1\n",
    "\n",
    "        t = list(d.keys())\n",
    "        count = 0\n",
    "        l = len(t)\n",
    "        for i in range(l - 2):\n",
    "            for j in range(i + 1, l - 1):\n",
    "                for k in range(j + 1, l):\n",
    "                    count += d[t[i]] * d[t[j]] * d[t[k]]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        n = len(nums)\n",
    "        ans = a = 0\n",
    "        for b in cnt.values():\n",
    "            c = n - a - b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        i = j = 0\n",
    "        while i < n:\n",
    "            while j < n and nums[j] == nums[i]:\n",
    "                j += 1\n",
    "            res += i * (j - i) * (n - j)\n",
    "            i = j\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        for i in range (len(nums)-2):\n",
    "            for j in range(i+1, len(nums)-1):\n",
    "                k = len(nums) - 1\n",
    "                while j < k:\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        count += 1\n",
    "                        k -= 1\n",
    "                    else:\n",
    "                        k -= 1\n",
    "                        while nums[k] == nums[k+1] and j < k:\n",
    "                            k -= 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-2):\n",
    "            for L in range(i+1,n-1):\n",
    "                if nums[i] != nums[L]:\n",
    "                    R = n - 1\n",
    "                    while L < R:\n",
    "                        if nums[L] != nums[R] and nums[i] != nums[R]:\n",
    "                            ans += 1\n",
    "                        R -= 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        ans=0\n",
    "        va=[]\n",
    "        s=Counter(nums)\n",
    "        for value in s.values():\n",
    "            va+=[value]\n",
    "        for i in range(len(set(nums))):\n",
    "            for j in range(i+1,len(set(nums))):\n",
    "                for k in range(j+1,len(set(nums))):\n",
    "                    ans+=va[i]*va[j]*va[k]\n",
    "\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        n = len(nums)\n",
    "        ans = a = 0\n",
    "        for b in cnt.values():\n",
    "            c = n - a -b\n",
    "            ans += a*b*c\n",
    "            a += b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        # nums.sort()\n",
    "        # res = 0\n",
    "        # n = len(nums)\n",
    "        # i = j = 0\n",
    "        # while i < n:\n",
    "        #     while j < n and nums[j] == nums[i]:\n",
    "        #         j += 1\n",
    "        #     res += i * (j - i) * (n - j)\n",
    "        #     i = j\n",
    "        # return res\n",
    "        \n",
    "        count = Counter(nums)\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for _, v in count.items():\n",
    "            res += t * v * (n - t - v)\n",
    "            t += v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1,n-1):\n",
    "                if nums[i]!=nums[j]:\n",
    "                    for k in range(j+1,n):\n",
    "                        if nums[k]!=nums[i] and nums[k]!=nums[j]:\n",
    "                            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        ans=0\n",
    "        for i in range(l):\n",
    "            for j in range(i, l):\n",
    "                for k in range(j, l):\n",
    "                    if nums[i]!=nums[j] and nums[i]!=nums[k] and nums[k]!=nums[j]:\n",
    "                        ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        result = 0\n",
    "        i = j = 0\n",
    "        n = len(nums)\n",
    "        while i < n:\n",
    "            while j < n and nums[j] == nums[i]:\n",
    "                j+=1\n",
    "            #print (i,j)\n",
    "            result += i * (j - i) * (n - j) \n",
    "            i = j\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        pre = nums[0]\n",
    "        count = 1\n",
    "        numList = []\n",
    "        for i in nums[1:]:\n",
    "            if i == pre:\n",
    "                count += 1\n",
    "            else:\n",
    "                numList.append(count)\n",
    "                count = 1\n",
    "            pre = i\n",
    "        \n",
    "        numList.append(count)\n",
    "        if len(numList) <= 2:\n",
    "            return 0\n",
    "        \n",
    "        unequalNum = 0\n",
    "        for i in combinations(numList,3):\n",
    "            unequalNum += i[0] * i[1] * i[2]\n",
    "        \n",
    "        return unequalNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1,n):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        res=res+1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter(nums)\n",
    "        n = len(nums)\n",
    "        b = 0\n",
    "        for _, v in cnt.items():\n",
    "            ans += v * b * (n - v - b)\n",
    "            b += v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            for j in range(i+1,len(nums)-1):\n",
    "                for k in range(j+1,len(nums)):\n",
    "                    if nums[i]!=nums[j] and nums[j]!=nums[k] and nums[i]!=nums[k]:\n",
    "                        cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        a=0\n",
    "        b=0\n",
    "        for i in nums[0:]:\n",
    "            b+=1\n",
    "            c=b\n",
    "            for j in nums[b:]:\n",
    "                c+=1\n",
    "                if i!=j:\n",
    "                    if c<len(nums):\n",
    "                        for k in nums[c:]:\n",
    "                            if i!=k and j!=k:\n",
    "                                a+=1\n",
    "                    else:\n",
    "                        break\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = Counter(nums)\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for _, v in count.items():\n",
    "            res += t * v * (n - t - v)\n",
    "            t += v\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                for k in range(j, len(nums)):\n",
    "                    if nums[i] != nums[j] and nums[j] != nums[k] and nums[k] != nums[i]:\n",
    "                        count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        #4:3, 2:1, 3:1\n",
    "        #\n",
    "        \n",
    "        '''\n",
    "        len_set = len(set(nums))\n",
    "        if len_set < 3:\n",
    "            return 0\n",
    "        count = {}\n",
    "        \n",
    "        for i in nums:\n",
    "            count[i] = count.get(i, 0) + 1\n",
    "        '''\n",
    "        count = Counter(nums)\n",
    "        ans = temp = 0\n",
    "        for i in count.values():\n",
    "            ans += temp * i * (len(nums) - temp - i)\n",
    "            temp += i\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def unequalTriplets(self, nums: list[int]) -> int:\r\n",
    "        n = 0\r\n",
    "        for i in range(len(nums)-2):\r\n",
    "            for j in range(i+1,len(nums)-1):\r\n",
    "                for k in range(j+1,len(nums)):\r\n",
    "                    if(nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]):\r\n",
    "                        n += 1\r\n",
    "        return n\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            for j in range(i+1,len(nums)-1):\n",
    "                for k in range(j+1,len(nums)):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        start = 0 # 中间数字的起始\n",
    "        for i in range(n-1):\n",
    "            # 枚举中间数\n",
    "            if nums[i] != nums[i+1]:\n",
    "                ans += start * (i-start+1) * (n-i-1)\n",
    "                start = i+1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        length = len(nums)\n",
    "        n = 0\n",
    "        for i in range(length):\n",
    "            dic[i] = nums[i]\n",
    "        \n",
    "        for i in range(length):\n",
    "            for j in range(length):\n",
    "                for k in range(length):\n",
    "                    if dic[i] < dic[j] < dic[k]:\n",
    "                        n += 1\n",
    "        return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                for k in range(j+1, n):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                for k in range(j,n):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        result +=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        n = len(nums)\n",
    "        ans = a = 0\n",
    "        for b in cnt.values():\n",
    "            c = n - a - b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    if nums[i] != nums[j] and nums[j] != nums[k] and nums[k] != nums[i]:\n",
    "                        count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        t = 0\n",
    "        result = 0\n",
    "        for _, num in cnt.items():\n",
    "            result += t * num * (len(nums) - t - num)\n",
    "            t += num\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        # 比当前小的元素数目a\n",
    "        # 当前元素数目b\n",
    "        # 比当前大的元素数目c\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter(nums)\n",
    "        a, c = 0, n\n",
    "        for _, b in cnt.items():\n",
    "            c -= b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                for k in range(j+1,len(nums)):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = Counter(nums)\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for v in count.values():\n",
    "            res += t * v * (n - t - v)\n",
    "            t += v\n",
    "        return res\n",
    "# 使用Counter函数，按照nums各个元素出现次数形成哈希表\n",
    "# 以v作为指针，记录三元组的中间数对应的出现次数，t记录v指针当前左边全部元素对应的出现次数，n-t-v记录v指针当前右边全部元素对应的出现次数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: list[int]) -> int:\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i,len(nums)):\n",
    "                for k in range(j,len(nums)):\n",
    "                    if 0 <= i < j < k < len(nums) and nums[i]!=nums[j] and nums[i]!=nums[k] and nums[j]!=nums[k]:\n",
    "                        result+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def backtracking(start, path):\n",
    "            if len(path) == 3:\n",
    "                if len(set(path)) == 3:  # Check for inequality\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            count = 0\n",
    "            for i in range(start, len(nums)):\n",
    "                if len(path) > 3:\n",
    "                    break\n",
    "                path.append(nums[i])\n",
    "                count += backtracking(i + 1, path)\n",
    "                path.pop()\n",
    "            \n",
    "            return count\n",
    "\n",
    "        count = backtracking(0, [])\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                for k in range(j+1,len(nums)):\n",
    "                    if nums[i]!=nums[j] and nums[j]!=nums[k] and nums[i]!=nums[k]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    if nums[i] == nums[j] or nums[i] == nums[k] or nums[j] == nums[k]:\n",
    "                        continue\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for i in range(n - 2):\n",
    "            for j in range(i + 1, n - 1):\n",
    "                if nums[i] == nums[j]:\n",
    "                    continue\n",
    "                for k in range(j + 1, n):\n",
    "                    if nums[j] == nums[k]:\n",
    "                        continue\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    if nums[i] != nums[j] and nums[j] != nums[k] and nums[k] != nums[i]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        h = defaultdict(int)\n",
    "        for num in nums:\n",
    "            h[num] += 1\n",
    "        \n",
    "        keys = list(h.keys())\n",
    "        m = len(keys)\n",
    "        if m < 3:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(m-2):\n",
    "            for j in range(i+1, m-1):\n",
    "                for k in range(j+1, m):\n",
    "                    res += h[keys[i]] * h[keys[j]] * h[keys[k]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        dic = Counter(nums)\n",
    "        n = len(nums)\n",
    "        ans, a = 0, 0\n",
    "        for b in dic.values():\n",
    "            c = n - a - b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                for k in range(j+1, n):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = Counter(nums)\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for _, v in count.items():\n",
    "            res += t * v * (n - t - v)\n",
    "            t += v\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        anw = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1,len(nums)):\n",
    "                for k in range(j + 1,len(nums)):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        anw += 1\n",
    "        return anw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        print(cnt)\n",
    "        n = len(nums)\n",
    "        ans = a = 0\n",
    "        for b in cnt.values():\n",
    "            c = n - a - b\n",
    "            ans += a * b * c\n",
    "            a += b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        count = 0\n",
    "        for i in range(length-2):\n",
    "            for j in range(i,length-1):\n",
    "                if nums[j] == nums[i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    for k in range(j,length):\n",
    "                        if nums[k] == nums[j] or nums[k] == nums[i] :\n",
    "                            continue\n",
    "                        else:\n",
    "                            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = Counter(nums)\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for _, v in count.items():\n",
    "            # t = 左边可以选的数量 v = 当前数数量 (n−t−v) = 右边可选数数量\n",
    "            res += t * v * (n - t - v)\n",
    "            t += v\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range( len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                for k in range(j+1, len(nums)):\n",
    "                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:\n",
    "                        ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        ans = start = 0\n",
    "        nums.sort()\n",
    "        for i,(x,y) in enumerate(pairwise(nums)):\n",
    "            if x == y: continue\n",
    "            ans += (i-start+1) * start * (len(nums)-1-i)\n",
    "            start = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        if len(set(nums))<3:\n",
    "            return 0\n",
    "        n=len(nums)\n",
    "        ret=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1,n):\n",
    "                    if nums[i]!=nums[j] and nums[j]!=nums[k] and nums[i]!=nums[k]:\n",
    "                        #print(i,nums[i],j,nums[j],k,nums[k])\n",
    "                        ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-2):\n",
    "            for i_j in range(i+1, n-1):\n",
    "                if nums[i] != nums[i_j]:\n",
    "                    for j in (i_j, n-1):\n",
    "                        for j_k in range(j+1, n):\n",
    "                            if nums[j_k] != nums[j] and nums[j_k] != nums[i]:\n",
    "                                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def unequalTriplets(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def backtracking(start, path):\n",
    "            if len(path) == 3:\n",
    "                if len(set(path)) == 3:  # Check for inequality\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            count = 0\n",
    "            for i in range(start, len(nums)):\n",
    "                if len(path) > 3:\n",
    "                    break\n",
    "                elif len(path) == 3:\n",
    "                    if len(set(path)) < 3: break\n",
    "                path.append(nums[i])\n",
    "                count += backtracking(i + 1, path)\n",
    "                path.pop()\n",
    "            \n",
    "            return count\n",
    "\n",
    "        count = backtracking(0, [])\n",
    "        return count\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
